看到了大神的題目解說
來練練binary lifting這個神奇的東西
感覺上應是基於dp上可以再更優化空間/查找時間的辦法

Maximize Value of Function in a Ball Passing Game

Q: https://leetcode.com/problems/maximize-value-of-function-in-a-ball-passing-game/

/**
    dp[i][n] -> i player when n round value
    dp[i][n] = dp[receiver[i]][n-1] + i;
 
*/
class Solution {
    public long getMaxFunctionValue(List<Integer> receiver, long k) {
        int temp_k = (int) k;
        int[][] dp = new int[receiver.size()][temp_k+1];
        for (int i = 0;i < receiver.size();i++) {
            dp[i][0] = receiver.get(i);
        }

        for (int x = 1;x <= temp_k;x++) {
            for (int i = 0;i < receiver.size();i++) {
                dp[i][x] = dp[receiver.get(i)][x-1] + i;
            }
        }

        int max = 0;
        for (int i = 0;i < receiver.size();i++) {
            if (max < dp[i][temp_k]) {
                max = dp[i][temp_k];
            }
        }
        return max;
    }
}

但這題困難在 k 為long值
因此要用binary lifting來處理縮小空間

/**
    dp[i][n] -> i player n round value
    dp[i][n] = dp[i][n-1] + dp[pos[i][n-1]][n-1];

    position[i][n] -> i player play 2^n round
    position[i][n] = position[position[i][n-1]][n-1]
 
*/
class Solution {
    public long getMaxFunctionValue(List<Integer> receiver, long k) {
        
        int n = 0;
        long tempK = k;
        while (tempK > 0) {
            n++;
            tempK /= 2;
        }
        int m = receiver.size();
        long[][] dp = new long[m][n+1];
        int[][] pos = new int[m][n+1];
        for (int i = 0;i < m;i++) {
            dp[i][0] = receiver.get(i);
            pos[i][0] = receiver.get(i);
        }
        for (int x = 1;x < n;x++) {
            for (int i = 0;i < m;i++) {
                pos[i][x] = pos[pos[i][x-1]][x-1];
                dp[i][x] = dp[i][x-1] + dp[pos[i][x-1]][x-1];
            }
        }
        long max = 0;
        List<Integer> bits = new ArrayList<>();
        for (int i = 0;i < n;i++) {
            if ((k >> i & 1l) != 0) {
                bits.add(i);
            }
        }

        for (int i = 0;i < m;i++) {
            long val = i;
            int now = i;
            for (int b : bits) {
                val += dp[now][b];
                now = pos[now][b];
            }
            max = Math.max(max, val);
        }


        return max;
    }
}

繼續刷graph題目....

Longest Increasing Path in a Matrix

Q: https://leetcode.com/problems/longest-increasing-path-in-a-matrix/

dfs

class Solution {

    int max = 1;

    public int longestIncreasingPath(int[][] matrix) {
        for(int i = 0;i < matrix.length;i++) {
            for (int j = 0;j < matrix[i].length;j++) {
                boolean[][] visted = new boolean[matrix.length][matrix[0].length];
                visted[i][j] = true;
                helper(matrix, visted, 1, i, j, -1);
            }
        }
        return max;
    }

    private void helper(int[][] matrix, boolean[][] visted, 
                        int length, int row, int col, int previous) {
        if (matrix[row][col] > previous) {
            int[][] directions = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
            for (int[] direction : directions) {
                int newRow = row + direction[0];
                int newCol = col + direction[1];
                if (newRow >= 0 && newCol >= 0 && newRow < matrix.length && newCol < matrix[row].length) {
                    length++;
                    visted[newRow][newCol] = true;
                    helper(matrix, visted, length, newRow, newCol, matrix[row][col]);
                    visted[newRow][newCol] = false;
                    length--;
                }
            }
        } else {
            length--;
            max = Math.max(max, length);
        }
    }
}

time limit T__T

add memo
I don't need to use visted (because it is increasing number list)

// DFS + Memoization Solution
// Accepted and Recommended
public class Solution {
    private static final int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    private int m, n;

    public int longestIncreasingPath(int[][] matrix) {
        if (matrix.length == 0) {
            return 0;
        }
        m = matrix.length; 
        n = matrix[0].length;
        int[][] memo = new int[m][n];
        int ans = 0;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                ans = Math.max(ans, dfs(matrix, i, j, memo));
            }
        } 
        return ans;
    }

    private int dfs(int[][] matrix, int i, int j, int[][] memo) {
        if (memo[i][j] != 0) return memo[i][j];
        for (int[] d : dirs) {
            int x = i + d[0], y = j + d[1];
            if (0 <= x && x < m && 0 <= y && y < n && matrix[x][y] > matrix[i][j]) {
                memo[i][j] = Math.max(memo[i][j], dfs(matrix, x, y, memo));
            }
                
        }
        memo[i][j]++;
        return memo[i][j];
    }
}

小總結

graph裡面 觀察路線的組成方式 visted必不是總要有 重要的是不要走回頭路
用暫存陣列可以很有效的提升graph遍利速度